package club.xiaojiawei.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/14/22 7:03 PM
 * @question 210. 课程表 II
 * @description 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
 * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组
 */
public class FindOrder210 {

    public static void main(String[] args) {
        FindOrder210 test = new FindOrder210();
        int[] result = test.findOrder2(4, new int[][]{{1, 0}, {2, 0}, {3, 1}, {3, 2}});
        System.out.println(Arrays.toString(result));
    }

    /**
     * bfs
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
//        存储每个节点的入度
        int[] inDegree = new int[numCourses];
//        存储每个节点的出度
        ArrayList<List<Integer>> outDegree = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            outDegree.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            outDegree.get(prerequisite[1]).add(prerequisite[0]);
            inDegree[prerequisite[0]]++;
        }
//        存储入度为0的节点
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0){
                queue.add(i);
            }
        }
        int index = 0;
        while (!queue.isEmpty()){
            Integer pop = queue.pop();
            result[index++] = pop;
            List<Integer> temp = outDegree.get(pop);
            for (Integer integer : temp) {
                if (--inDegree[integer] == 0){
                    queue.add(integer);
                }
            }
        }
        return index == numCourses? result : new int[]{};
    }

    /**
     * dfs
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder2(int numCourses, int[][] prerequisites) {
        int[] result = new int[numCourses];
//        存储每个节点的出度
        ArrayList<List<Integer>> outDegree = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            outDegree.add(new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            outDegree.get(prerequisite[1]).add(prerequisite[0]);
        }
//        标志某个点的状态：0表示未搜索，1表示正在搜索，等待回溯中，2表示已经搜索完毕
        int[] sign = new int[numCourses];
        this.count = numCourses;
        for (int j = 0; j < numCourses && count != -1; j++) {
            if (sign[j] == 0){
                reversion(result, sign, j, outDegree);
            }
        }
        return count == 0? result : new int[]{};
    }

    int count;
    public void reversion(int[] result, int[] sign, int index, List<List<Integer>> out){
        sign[index] = 1;
        List<Integer> temp = out.get(index);
        for (int integer : temp) {
            if (sign[integer] == 0){
                reversion(result, sign, integer, out);
                if (count == -1){
                    return;
                }
            }else if (sign[integer] == 1){
                count = -1;
                return;
            }
        }
        result[--count] = index;
        sign[index] = 2;
    }
}
